package org.schat;

import java.util.Date;

/**
 * @Description 斐波那契数列
 * @Author lsh
 * @Date 2020/3/19 13:54
 **/
public class Fib extends Date {

    public static void main(String[] args) {
        System.out.println(dpFib(1000));
    }

    static int fib(int n){
      int[] remember = new int[n+1];
      return help(n,remember);
    }

    static int help(int n,int[] remember){
        if(n  == 1 || n == 2){
            return 1;
        }
        if(remember[n] == 0){
            remember[n] = fib(n-1) + fib(n - 2);
        }
        return remember[n] ;
    }

    static int dpFib(int n){
        int[] dp= new int[n+1];
        dp[1] = dp[2] = 1;
        for(int i = 3;i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    static void fib(){
        long fib1 = 0;
        long fib2 = 0;
        for(int i = 1; i <= 100; i ++){
            if( i ==1 || i ==2){
                fib1 = 1;
                fib2 = 1;
            }else{
                long teamp = fib2;
                fib2 = fib2 + fib1;
                fib1 = teamp;
            }
            System.out.print(fib2 +" ");
        }
    }
}
